package Graph;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

/**
 * The graph class.  The meat and potatoes and dessert of the planarity
 * testing algorithm resides here.
 * 
 * @author Thomas Batzold and Ryan H Lewis.
 *
 */
public class Graph {
	
	/*
	 * Data structures to store graph information.
	 */
	private Map<Vertex , Set<Vertex>> adjList = new HashMap<Vertex, Set<Vertex>>();
	private List<Vertex> vertList = new LinkedList<Vertex>();
	private List<Edge> edgeList = new LinkedList<Edge>();
	
	// A Global variable so that certain vertices will always have a unique label
	private static int global = 0;

	/*
	 * Private Edge class used to construct adjacency list.
	 */
	private class Edge{
		private Vertex v;
		private Vertex u;
		public Edge(Vertex u, Vertex v){
			this.v = v;
			this.u = u;
		}
		
		public Vertex getU(){
			return u;
		}
		
		public Vertex getV(){
			return v;
		}
		
		public boolean equals(Object o){
			if (o instanceof Edge){
				return (((((Edge)o).u.equals(this.u)) && (((Edge)o).v.equals(this.v))) || ((((Edge)o).u.equals(this.v)) && (((Edge)o).v.equals(this.u)))); 
			}
			return false;
		}
		
		public String toString(){
			return "[" + u + ", " + v + "]";
		}
		
	}

	
	public Graph(String file) {
		adjList = new HashMap<Vertex, Set<Vertex>>();
		vertList = new LinkedList<Vertex>();
		edgeList = new LinkedList<Edge>();
		try{
			BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(file)));
			String line = br.readLine();
			while (line != null){
				
				String [] e = line.split(" ");
				if (e.length != 2){
					throw new Exception("Invalid Edge!");
				}else{
					Vertex u = new Vertex(e[0]);
					Vertex v = new Vertex(e[1]);
					Vertex v_p = u;
					Vertex u_p = v;
					if (!vertList.contains(u)){
						vertList.add(u);
					}
					if (!vertList.contains(v)){
						vertList.add(v);
					}
					u_p = vertList.get(vertList.indexOf(u));
					v_p = vertList.get(vertList.indexOf(v));
				
					edgeList.add(new Edge(u_p, v_p));
				}
				line = br.readLine();
			}
			GenerateAdjacencyList();
		}catch(Exception e){
			e.printStackTrace();
		}
		
	}
	
	/**
	 * Build a new graph based on 'g'
	 * 
	 * @param g
	 */
	public Graph(Graph g){
		this.adjList = new HashMap<Vertex, Set<Vertex>>();
		this.adjList.putAll(g.getAdjacencyList());
		this.vertList.addAll(g.getVertList());
		this.edgeList.addAll(g.getEdgeList());
	}
	
	/**
	 * Create a graph from a list of vertices 'c' that forms a Cycle in the graph G
	 * @param c the list of vertices in the cycle, in the order they appear in the cycle
	 */
	public Graph(List<Vertex> c){
		vertList = c;
		edgeList = new LinkedList<Edge>();
		for (int i = 0; i < vertList.size() - 1; i++){
			edgeList.add(new Edge(vertList.get(i), vertList.get(i+1)));
		}
		HashSet<Vertex> reduceVerts = new HashSet<Vertex>(c);
		vertList.clear();
		vertList.addAll(reduceVerts);
		GenerateAdjacencyList();
	}
	
	
	public Graph(){
		adjList = new HashMap<Vertex, Set<Vertex>>();
	}
	
	/**
	 * Add the graph 'g' to this graph.
	 * @param g
	 * @return
	 */
	public Graph combine(Graph g){
		Graph ret = new Graph();
		ret.vertList.addAll(this.vertList);
		ret.edgeList.addAll(this.edgeList);
		for (Vertex v: g.vertList){
			if (!ret.getVertList().contains(v)){
				ret.vertList.add(v);
			}
		}
		for (Edge e: g.edgeList){
			if (!ret.getEdgeList().contains(e)){
				ret.edgeList.add(e);
			}
		}
		ret.GenerateAdjacencyList();
		return ret;
	}
	
	/**
	 * Generate an adjacency list for the graph based on its current Edge and Vertex lists.
	 */
	public void GenerateAdjacencyList(){
		adjList.clear();
		for (Vertex v: vertList){
			v.setDegree(0);
			adjList.put(v, new HashSet<Vertex>());
		}
		for (Vertex v: vertList){
			for (Edge e: edgeList){
				if (v.equals(e.getU())){
					Vertex temp = vertList.get(vertList.indexOf(e.getV()));
					adjList.get(v).add(temp);
					adjList.get(temp).add(v);
					v.setDegree(v.getDegree() + 1);
					temp.setDegree(temp.getDegree() + 1);
				}
			}
		}
	}
	
	/**
	 * Find a cycle in the Graph g
	 * 
	 * @return A cycle in the calling graph
	 */
	public Graph FindCycle(){
		Object[] keys = adjList.keySet().toArray();
		Random r = new Random();
		Object swap;
		int nextInt = 0;
		for (int i = 0; i < keys.length; i++){
			nextInt = r.nextInt(keys.length);
			swap = keys[i];
			keys[i] = keys[nextInt];
			keys[nextInt] = swap;
		}
		
		for (Object v : keys){
				((Vertex) v).setColor(Vertex.WHITE);
				((Vertex) v).setParent(null);
		}
		for (Object u: keys){
			if (((Vertex) u).getColor().equals(Vertex.WHITE)){
				List<Vertex> c = DFSVisit(((Vertex) u), null);
				if (c != null && !c.get(0).equals(c.get(c.size()-1))){
					c.add(c.get(0)); 
				}
				//print("Back From DFSVisit");
				if (c != null){					
					return new Graph(c);
				}
			}
		}
		return null;
	}
	
	/**
	 * Test whether this graph is a PATH by checking whether the degree of at most two vertices is one
	 */ 
	public boolean testPath(){
//		print("Testing Pathity");
		boolean retVal = true;
		int count = 0;
		// Test degenerate path (1 Vertex)
		if (vertList.size() == 1){
			return true;
		}
		for (Vertex v: vertList){
			if(v.getDegree() == 1){
				count++;
				retVal = retVal && true;
			}
			else if(v.getDegree() == 2){
				retVal = retVal && true;
			}
			else{
				retVal = retVal && false;
			}
		}
		if (count != 2){
			return false;
		}
		return retVal;
	}
	
	/**
	 * Visit a vertex 'u' in the graph 'g'
	 * 
	 * @param u - the vertex to visit
	 * @param g - the Graph where g exists
	 */
	private List<Vertex> DFSVisit(Vertex u, Vertex parent){		
		u.setColor(Vertex.GRAY);
		List<Vertex> visit = null;
		for (Vertex v : this.adjList.get(u)){
			if (v.getColor().equals(Vertex.WHITE)){
				/**
				 * v is a vertex adjacent to u which is not yet visited
				 */
				v.setParent(u);
				visit = DFSVisit(v, u);
				if (visit != null){
					if (!visit.contains(v) || visit.get(0).equals(v)){
						if(!visit.get(0).equals(visit.get(visit.size()-1)) ||  visit.size() == 1){
							visit.add(v);
						}
					}
					return visit;
				}
			}
			else if (v.equals(parent)){
				// Ignore the ones we've seen so far?
				continue;
			}
			else if (v.getColor().equals(Vertex.GRAY)){
				visit = new LinkedList<Vertex>();
				visit.add(v);
				return visit;
			}
		}
		return null;
	}
	
	/**
	 * Takes a list of vertices in G and induces a subgraph
	 * @param h
	 * @param G
	 * @return
	 */
	private Graph subGraph(LinkedList<Vertex> h, Graph g){
		Graph sub = new Graph();
		sub.vertList.addAll(h);
		for (Vertex v: h){
			for (Vertex u: g.vertList){
				Edge e = new Edge(v, u);
				if (g.edgeList.contains(e)){
					if (!sub.edgeList.contains(e)){
						sub.edgeList.add(g.edgeList.get(edgeList.indexOf(e)));
					}
				}
			}
		}
		sub.GenerateAdjacencyList();
		return sub;
		
	}
	
	/**
	 *  non-recursive function which 
	 *  constructs a list of connected components (which are lists)
	 * @return
	 */
	public LinkedList<Graph> connectedComponents(Graph cycle){
		LinkedList<Graph> cc = new LinkedList<Graph>(); 
		for (Vertex v: this.adjList.keySet()){
			if (!v.getColor().equalsIgnoreCase("v") && !cycle.contains(v)){
				cc.add(this.subGraph(doConnectedComponents(v, cycle),this));
			}
		}
		// Remove nulls from cc...
		LinkedList<Graph> components = new LinkedList<Graph>();
		for (Graph g: cc){
			if (g != null){
				components.add(g);
			}
		}
		return components;
	}
	/**
	 *  a recursive function which constructs a linked list
	 * @param v
	 * @return
	 */
	private LinkedList<Vertex> doConnectedComponents(Vertex v, Graph c){
		v.setColor("v");
		LinkedList<Vertex> vList = new LinkedList<Vertex>();
		vList.add(v);
		for (Vertex u: this.adjList.get(v)){
			if (!u.getColor().equalsIgnoreCase("v") && !c.contains(u)){
				vList.addAll(this.doConnectedComponents(u, c));
			}
		}	
		return vList;
		
	}

	/**
	 * Find the pieces of the Graph g with respect to Cycle c
	 * 
	 * @param g The graph to find pieces of
	 * @param c The Cycle to find pieces with respect to
	 * @return
	 */
	public List<Graph> findPieces(Graph c){
		List<Graph> pieces = new LinkedList<Graph>();
		List<Vertex> nonCycleVerts = new LinkedList<Vertex>();
		nonCycleVerts.addAll(this.vertList);
		nonCycleVerts.removeAll(c.vertList);
		List<Vertex> visitedVerts = new LinkedList<Vertex>();
		for (Vertex v: nonCycleVerts){
			if (!visitedVerts.contains(v)){
				Graph piece = new Graph();
				piece.vertList.add(v);
				visitedVerts.add(v);
				Queue<Vertex> q = new LinkedList<Vertex>();
				q.add(v);
				Vertex s = v;
				for (Vertex k: vertList){
					k.setColor(Vertex.WHITE);
				}
				s.setColor(Vertex.GRAY);
				while (!q.isEmpty()){
					s = q.poll();
					for (Vertex t: adjList.get(s)){
						if (t.getColor().equals(Vertex.WHITE)){
							piece.vertList.add(t);
							piece.edgeList.add(new Edge(s, t));
							if (!c.contains(t)){
								q.add(t);
							}
							visitedVerts.add(t);
							t.setColor(Vertex.GRAY);
						}
						else if(piece.vertList.contains(t)){
							Edge e = new Edge(s, t);
							if (!piece.edgeList.contains(e)){
								piece.edgeList.add(new Edge(s, t));
							}
						}
					}
					s.setColor(Vertex.BLACK);
				}
				piece.GenerateAdjacencyList();
				pieces.add(piece);
			}
		}
		Graph piece = null;
		for (Vertex v: c.vertList){
			v.setColor(Vertex.WHITE);
		}
		for (Vertex v: c.vertList){
			piece = null;
			if (v.getColor().equals(Vertex.WHITE)){
				v.setColor(Vertex.GRAY);
				
				for (Edge e: edgeList){
					if (e.getU().equals(v) && !c.edgeList.contains(e) && c.vertList.contains(e.getV())){
						piece = new Graph();
						piece.vertList.add(v);
						piece.edgeList.add(e);
						piece.vertList.add(e.getV());
						e.getV().setColor(Vertex.GRAY);
					}
				}
			}
			if (piece != null){
				piece.GenerateAdjacencyList();
				pieces.add(piece);
			}
		}
		
		
		return pieces;
	}
	
	/**
	 * Remove the vertex v from this graph, as well as all edges adjacent to v.
	 * @param v
	 * @return
	 */
	public Graph removeVertex(Vertex v){
		List<Vertex> newVertList = new LinkedList<Vertex>();
		newVertList.addAll(this.vertList);
		newVertList.remove(v);
		List<Edge> newEdgeList = new LinkedList<Edge>();
		newEdgeList.addAll(this.edgeList);
		List<Edge> edgesToRemove = new LinkedList<Edge>();
		for (Edge e : newEdgeList){
			if (e.getU().equals(v) || e.getV().equals(v)){
				edgesToRemove.add(e);
			}
		}
		newEdgeList.removeAll(edgesToRemove);
		Graph g = new Graph();
		g.edgeList = newEdgeList;
		g.vertList = newVertList;
		g.GenerateAdjacencyList();
		return g;
	}
	
	
	private Graph removeEdge(Edge e){
		Edge e_rev = new Edge(e.getV(), e.getU());
		if (edgeList.contains(e)){
			edgeList.remove(e);
		}
		if (edgeList.contains(e_rev)){
			edgeList.remove(e_rev);
		}
		List<Vertex> newVertList = new LinkedList<Vertex>();
		newVertList.addAll(vertList);
		List<Edge> newEdgeList = new LinkedList<Edge>();
		newEdgeList.addAll(edgeList);
		Graph g = new Graph();
		g.edgeList = newEdgeList;
		g.vertList = newVertList;
		g.GenerateAdjacencyList();
		return g;
		
	}
	
	
	/**
	 * Find the first common element between the stack a and the queue v
	 * @param a
	 * @param b
	 * @return
	 */
    public static Object FirstCommonElement(Stack<Vertex> a, Queue<Vertex> b){
    	for (Vertex x : a){
    		if (b.contains(x)){
    			return x;
    		}
    	}
    	return null;
    	
    }
    
    /**
     * Test the graph g for bipartite.
     * @return true - if the graph is bipartite, false otherwise.
     */
    public boolean TestBipartite(){
    	// Get the start Vertex
    	if (this.vertList.size()  < 3){
    		return true;
    	}
    	Vertex s = this.vertList.get(0);
    	// Set up data structures.
    	Queue<Vertex> q = new LinkedList<Vertex>();
    	Set<Vertex> p_1 = new HashSet<Vertex>();   // Red Partition
    	Set<Vertex> p_2 = new HashSet<Vertex>();   // Blue Partition
    	s.setColor("Red");
	    	for (Vertex u : this.getVertList()){
	    		if (u != s){
	    			u.setColor(Vertex.WHITE);
	    		}
	    	}
	    	q.add(s);
	    	Set<Vertex> p_i;
	    	String currColor;
	    	while (!q.isEmpty()){
	    		Vertex u = q.remove();
	    		if (u.getColor().equals("Blue")){
	    			p_i = p_2;
	    			currColor = "Red";
	    		}
	    		else{
	    			p_i = p_1;
	    			currColor = "Blue";
	    		}
	    		try{
	    		for (Vertex v: this.getAdjacencyList().get(u)){
	    			if (v.getColor().equals(Vertex.WHITE)){
	    				v.setColor(currColor);
	    				q.add(v);
	    				p_i.add(v);
	    			}
	    			else if (v.getColor().equals(u.getColor())){
	    				return false;
	    			}
	    			else{
	    				continue;
	    			}
	    		}
	    	}catch(NullPointerException npe){
	    		System.err.println(npe.getMessage());
	    	}
	    }

    	
    	

    	
    	return true;
    }
    public boolean isCycle(){
    	for (Vertex v : this.vertList){
    		if (this.adjList.get(v).size() != 2){
    			return false;
    		}
    	}
    	return true;
    }
    /**
     * This method should only be used on CYCLES.  This method takes a sub-path in the cycle and replaces it with a new
     * sub-path.
     * @param pathToReplace
     * @param replacement
     * @return
     */
    public Graph replacePath(List<Vertex> pathToReplace, List<Vertex> replacement){
    	Graph g = null;
    	//if the endpoints make sense
    	if (((pathToReplace.get(0).equals(replacement.get(0))) 
    			&& (pathToReplace.get(pathToReplace.size()-1).equals(replacement.get(replacement.size()-1))))){
    		Set<Vertex> newVerts = new HashSet<Vertex>();
    		Set<Vertex> oldVerts = new HashSet<Vertex>();
    		Set<Vertex> inter = new HashSet<Vertex>();
    		List<Edge> edgesToReplace = new LinkedList<Edge>();
    		List<Edge> newPathEdges = new LinkedList<Edge>();
    		
    		for (int i = 0; i  < pathToReplace.size(); i++)
    			oldVerts.add(pathToReplace.get(i));
    		for (int i = 0; i < replacement.size(); i++)
    			newVerts.add(replacement.get(i));
    			
    		for (int i = 0; i < pathToReplace.size() - 1 ; i++)
    			edgesToReplace.add(new Edge(pathToReplace.get(i), pathToReplace.get(i + 1)));	
    		
    		for (int i = 0; i < replacement.size() - 1 ; i++)
    			newPathEdges.add(new Edge(replacement.get(i), replacement.get(i + 1)));
 
    		g = new Graph(this); 
    		// This only works because it is run on cycles.
    		inter.addAll(oldVerts);
    		inter.retainAll(newVerts);
    		newVerts.removeAll(inter);
    		oldVerts.removeAll(inter);
    		for (Vertex v : oldVerts){
        		g = g.removeVertex(v);
        	}
    		//Check if it removed no vertices, and somehow left an edge in
			Edge work = new Edge(replacement.get(0),replacement.get(replacement.size()-1));
    		if (g.edgeList.indexOf(work) != -1){
    			g.edgeList.remove(g.edgeList.indexOf(work));
    		}
    		g.vertList.addAll(newVerts);
        	g.edgeList.addAll(newPathEdges);
    		g.GenerateAdjacencyList();
        	
    	}
    	return g;
    }

    /**
     * Get the attachment points of 'p' on this graph (Should be a cycle).
     * @param p
     * @return
     */
    public List<Vertex> getAttachmentPoints(Graph p){
    	List<Vertex> attachPts = null;
    	if (p!= null){
	    	attachPts = new LinkedList<Vertex>();	
	    	for (Vertex v: p.getVertList()){
		    		if (this.vertList.contains(v)){
		    			attachPts.add(v);
		    		}
	    	}
    	}
    	return attachPts;
    }
    
    /**
     * Return an InterlacementVertex for the piece p
     * @param p
     * @return
     */
    private InterlacementVertex getVertexByPiece(Graph p){
    	for (Vertex v : vertList){
    		if (((InterlacementVertex)v).getPiece().equals(p)){
    			return (InterlacementVertex)v;
    		}
    	}
    	return null;
    }
    
    public boolean contains(Vertex v){
    	return vertList.contains(v);
    }
    
    
    /*
     * Utility function for counting the number of attachment points along a cycle
     */
    private int countAttachmentsBeforeCollision(List<Vertex> cycle, Graph p_i, Graph p_j){
    	int count = 0;
    	
    	for (int i = 0; i < cycle.size(); i++){
    		Vertex c = cycle.get(i);
    		if (p_i.contains(c) && p_j.contains(c) && i == 0){
    			count++;
    		}
    		else {
	    		if (p_i.contains(c)){
	    			count++;
	    		}
	    		if (p_j.contains(c)){
	    			return count;
	    		}
    		}
    	}
    	return count;
    }
    
 
    
    /**
     * Create the interlacemnt graph for 'pieces' with respect to cycle.
     * @param cycle
     * @param pieces
     * @return
     */
    public Graph createInterlacementGraph(Graph cycle, List<Graph> pieces, boolean debug){
    	Graph ig = new Graph();
    	InterlacementVertex v_i;
    	InterlacementVertex v_j;
    	List<Vertex> attachPts;
    	Vertex s = null;
    	for (Graph p : pieces){ 
    		// Create an interlacement vertex for each piece p
    		ig.vertList.add(new InterlacementVertex(p, ((Integer)global).toString() ));
    		global++;
    	}
    	Random r = new Random();
    	for (int i = 0; i < pieces.size(); i++){
    		attachPts = cycle.getAttachmentPoints(pieces.get(i));
    		s = attachPts.get(r.nextInt(attachPts.size())); // a random attachement point for the piece p_i
    		for (int j = i+1; j < pieces.size(); j++){
    				 v_i = ig.getVertexByPiece(pieces.get(i));
    				 v_j = ig.getVertexByPiece(pieces.get(j));
    				 Edge e = new Edge(v_i, v_j);
    				 if (!ig.edgeList.contains(e)){
    					 // Permute cycle to start with s
    					 List<Vertex> reorderedVerts = new LinkedList<Vertex>(); // This code will take the verts of cycle and re-order them, into re-order verts
    					 Vertex temp = s;
    					 Vertex next = null;
    					 reorderedVerts.add(s);
     					 while (reorderedVerts.size() < cycle.vertList.size()){
    						 for (Vertex vert : cycle.adjList.get(temp)){
    							 if (!reorderedVerts.contains(vert)){
    								 reorderedVerts.add(vert);
    								 next = vert;
    								 break;
    							 }
    						 }
    						 temp = next;
    					 }
    					 List<Vertex> reversedVerts = new LinkedList<Vertex>();
    					 reversedVerts.addAll(reorderedVerts);
    					 reversedVerts.remove(0);
    					 Collections.reverse(reversedVerts);
    					 reversedVerts.add(0, reorderedVerts.get(0));
    					 int maxIVerts = attachPts.size();
    					 int iVertCount = 0;
    					 if (pieces.get(i).contains(s) && pieces.get(j).contains(s)){
    						 iVertCount = countAttachmentsBeforeCollision(reversedVerts, pieces.get(i), pieces.get(j));
    						 if (!(iVertCount == maxIVerts)){
    							 iVertCount = 0;
    							 iVertCount = countAttachmentsBeforeCollision(reorderedVerts, pieces.get(i), pieces.get(j));
    							 if (!(iVertCount == maxIVerts)){
    								 ig.edgeList.add(e);
    							 }
    						 }
    					 }
    					 else{
	    					 iVertCount = countAttachmentsBeforeCollision(reorderedVerts, pieces.get(i), pieces.get(j));
	    					 if (iVertCount < maxIVerts){
	    						 iVertCount += countAttachmentsBeforeCollision(reversedVerts, pieces.get(i), pieces.get(j)) - 1;
	    					 }
	    					 if (iVertCount < maxIVerts){
	    						 ig.edgeList.add(e);
	    					 }
    					 }
    			}
    		}
    	}
    	ig.GenerateAdjacencyList();
    	return ig;
    }
    
    
    
    
	/**
	 * Test whether the Graph G is planar
	 * 
	 * @param g	
	 * @return true if the graph is planar, false if not
	 */
	public static boolean TestPlanarity(Graph g, Graph cycle, List<Graph> pieces){
		boolean planar = true;
		if (g.getEdgeList().size() > ((3 * g.getVertList().size()) -6)){
			return false;
		}
		for (Graph piece : pieces){
			//degenerate end cases
			if(piece.vertList.size() == 1){
				planar = planar && true;
			}
			else if (piece.testPath()){
				planar = planar && true;
			}
			//now test recursively that all of our pieces are planar
			else{
				/*
				 * Find two consecutive attachment points of 'p' on the cycle.
				 */
				Random r = new Random();
				int a_index;// = r.nextInt(attach_pts.size());
				Vertex a;// = attach_pts.get(a_index);
				Vertex b;// = attach_pts.get((a_index + 1) % attach_pts.size());
				Graph cPrime = null;
				List<Vertex> attachPts = cycle.getAttachmentPoints(piece);
				List<Graph> morePieces = new LinkedList<Graph>();
				List<Vertex> cyclePath;
				List<Vertex> piecePath;
				Graph combine = cycle.combine(piece);
				// A flag for exiting the loop when our only piece is a path.
				boolean flag = false;
				while ((morePieces.size() <= 1) && !flag){
					if (!((morePieces.size() == 1) && morePieces.get(0).testPath())){
						a_index = r.nextInt(attachPts.size()); //get attachment points
						a = attachPts.get(a_index); //use a random number to get different cycles
						b = attachPts.get((a_index + 1) % attachPts.size());
						Graph tempPiece = new Graph(piece);
						for (Vertex v: attachPts){
							if (!v.equals(a) && !v.equals(b)){
								tempPiece = tempPiece.removeVertex(v);
							}
						}
						piecePath = tempPiece.findPath(a, b); //find the path that goes through the piece
						cyclePath = cycle.findPath(a, b); //find the path that goes through the cycle
						cPrime = cycle.replacePath(cyclePath, piecePath); //create C' our new cycle
						morePieces = combine.findPieces(cPrime); //find all the pieces relative to that cycle
					}else{
						flag = true;
					}
				}
				planar = (planar && TestPlanarity(combine, cPrime, morePieces)); //check if each sub-piece w.r.t c' of the piece is planar
				if (!planar){ //if any of the pieces are not-planar the graph isn't planar return false!
					return false;
				}
			}
		}
		if (planar == true){
			Graph ig = g.createInterlacementGraph(cycle, pieces, false); // if everything so far was planar return true iff the i.g. is bipartite
			return ig.TestBipartite();
		}
		return planar;
	}
	
	/**
	 * Find a path in this graph from 'u' to 'v'.  This method uses breadth-first search.
	 * @param u The starting vertex of the path.
	 * @param v The ending vertex of the path.
	 * @return
	 */
	public List<Vertex> findPath(Vertex u, Vertex v){
		Stack<Vertex> revPath = new Stack<Vertex>();
		List<Vertex> path = new LinkedList<Vertex>();
		for (Vertex a : this.vertList){
			a.setColor(Vertex.WHITE);
			a.setParent(null);
		}
		u.setColor(Vertex.GRAY);
		Queue<Vertex> q = new LinkedList<Vertex>();
		q.add(u);
		Vertex s = u;
		while (!q.isEmpty()){
			s = q.poll();
			if (s.equals(v)){ //if we have found a path
				break;
			}
			for (Vertex t: adjList.get(s)){
				if (t.getColor().equals(Vertex.WHITE)){
					t.setColor(Vertex.GRAY);
					t.setParent(s);
					q.add(t);
				}
			}
			
			s.setColor(Vertex.GRAY);
		}
		while (s != null){
			revPath.push(s);
			s = s.getParent();
		}
		path.addAll(revPath);
		return path;
	}
	
	
	public List<Vertex> findLongPath(Vertex u, Vertex v){
		Graph temp = new Graph(this);
		List<Vertex> path = findPath(u,v);
		path.remove(u);
		path.remove(v);
		for (Vertex s : path){
			temp = temp.removeVertex(s);
		}
		path = temp.findPath(u, v);
		return path;
	}
	
	
	public String toString(){
		String retVal = "\n(Vertices: {";
		for (Vertex v: vertList){
			retVal = retVal + v.toString() + ", ";
		}
		int lastIndex = retVal.lastIndexOf(',') > -1? retVal.lastIndexOf(','): retVal.length() - 1; 
		retVal = retVal.substring(0, lastIndex) + "}\nEdges: { ";
		for (Edge e: edgeList){
			retVal = retVal + "[" + e.getU() + ", " + e.getV() + "], ";
		}
		lastIndex = retVal.lastIndexOf(',') > -1? retVal.lastIndexOf(','): retVal.length() - 1; 
		retVal = retVal.substring(0, lastIndex ) + "} )";
		return retVal;
	}
	
	public Vertex getVertex(String label){
		for (Vertex u : vertList){
			if (u.getLabel().equals(label)){
				return u;
			}
		}
		return null;
	}

	public List<Vertex> getVertList(){
		return vertList;
	}
	
	public List<Edge> getEdgeList(){
		return edgeList;
	}
	
	public Map<Vertex, Set<Vertex>> getAdjacencyList(){
		return adjList;
	}
	
}
